package sort;

import linear.LinkedListUtil;
import linear.LinkedListUtil.ListNode;

public class SortLinkedList148 {
    public static ListNode merge(ListNode h1, ListNode h2) {
        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        while (h1 != null && h2 != null) {
            if (h1.val <= h2.val) {
                cur.next = h1;
                h1 = h1.next;
                cur = cur.next;
            } else {
                cur.next = h2;
                h2 = h2.next;
                cur = cur.next;
            }
            if (h1 != null) {
                cur.next = h1;
            } else if (h2 != null) {
                cur.next = h2;
            }
        }
        return sentinel.next;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        l1.next = new ListNode(3);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(5);
        ListNode merged = merge(l1, l2);
        LinkedListUtil.printLinkedList(merged);
    }

}
